package com.s4.queue;

public class ArrayQueue implements IQueue {

	protected static final int DEFAULT_LENGTH = 10;

	protected final Object[] datas;

	// head表示队头下标，
	protected int head = 0;
	// tail表示队尾下标
	protected int tail = head;

	public ArrayQueue() {
		this(DEFAULT_LENGTH);
	}

	public ArrayQueue(int length) {
		this.datas = new Object[length];
	}

	@Override
	public int getLength() {
		return this.tail - this.head;
	}

	@Override
	public int getPresetLength() {
		return this.datas.length;
	}

	/*
	 * 入队操作: 这个是优化后的方案。入队操作的时间复杂度还是 O(1)
	 */
	@Override
	public boolean enqueue(Object value) {
		if (this.isFull()) {
			if (this.head == 0) {
				return false;
			}
			// 进行迁移[head, tail) 左移 head 位
			for (int i = this.head; i < this.tail; i++) {
				this.datas[i - this.head] = this.datas[i];
			}
			// 搬移完之后更新 head 和 tail
			this.tail -= this.head;
			this.head = 0;
		}
		this.datas[this.tail] = value;
		this.tail++;
		return true;
	}

	// 入队操作: 这是一个错误示例，一个较差的方法
	public boolean enqueueBad(Object value) {
		if (this.isFull()) {
			return false;
		}
		this.datas[this.tail] = value;
		this.tail++;
		return true;
	}

	@Override
	public boolean isEmpty() {
		return this.head == this.tail;
	}

	@Override
	public boolean isFull() {
		return this.tail == this.datas.length;
	}

	/*
	 * 出队操作，复杂度是 O(1)
	 */
	@Override
	public Object dequeue() {
		if (this.isEmpty()) {
			return null;
		}
		Object ret = this.datas[this.head];
		this.head++;
		return ret;
	}

	/**
	 * 每次出队都会迁移，会增加时间复杂度为O(n)，因此不推荐这么做
	 */
	@Deprecated
	public Object dequeue2() {
		if (this.isEmpty()) {
			return null;
		}
		// 每次进行出队操作都相当于删除数组下标为 0 的数据
		Object ret = this.datas[0];
		// [1, tail -1] 整体左移一位 [1, tail) | [0, tail - 1)
		for (int i = 0; i < tail - 1; i++) {
			this.datas[i] = this.datas[i + 1];
		}
		this.tail--;
		this.datas[this.tail] = null;
		return ret;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(getClass().getSimpleName()).append(" [");
		for (int i = this.head; i < this.tail; i++) {
			stringBuilder.append(this.datas[i]);
			if (i + 1 == this.tail) {
				continue;
			}
			stringBuilder.append(", ");
		}
		stringBuilder.append(']');
		return stringBuilder.toString();
	}

	public static void main(String[] args) {
		IQueue queue = new ArrayQueue(3);
		System.out.println(queue.enqueue(1));
		System.out.println(queue.enqueue(2));
		System.out.println(queue.enqueue(3));
		System.out.println(queue.enqueue(5));
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.enqueue(7));
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.dequeue());
		System.out.println(queue);

		System.out.println(queue.enqueue(8));
		System.out.println(queue);
	}

}
